package com.javabasic.algorithm.tencent_interview;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/1/4 11:21 下午
 *
 * 三个方法：时间复杂度均为O(1)
 * 1. init(n) n为数组大小
 * 2. put(element) 往数组中添加元素
 * 3. get() 获取数组中所有元素的平均值
 */
public class CircularArray {

    public static void main(String[] args) {
        CustomStack customStack = new CustomStack(3);
        customStack.put(1);
        customStack.put(4);
        customStack.put(7);
        System.out.println(customStack.get());
        customStack.put(8);
        System.out.println(customStack.get());
        customStack.put(8);
        customStack.put(8);
        System.out.println(customStack.get());
    }
}


class CustomStack {
    private int sum;
    private int cap;
    private int[] data;
    private int checkPoint;
    private boolean cycle;

    public CustomStack(int cap) {
        init(cap);
    }


    public void init(int cap) {
        this.cap = cap;
        data = new int[cap];
        checkPoint = 0;
        sum = 0;
        cycle = false;
    }

    public void put(int element) {
        if (checkPoint >= cap) {
            checkPoint = 0;
            cycle = true;
        }

        if (cycle) {
            sum -= data[checkPoint];
        }

        sum += element;
        data[checkPoint++] = element;
    }

    public int get() {
        if (cycle) {
            return sum / cap;
        } else {
            return sum / checkPoint;
        }
    }
}